/*
300.最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=problem-list-v2&envId=binary-search
难度:中等  李佳韵  2024/09/06
二分查找
*/


#include <iostream>
#include <vector>

using namespace std;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 1)
            return 1;
        int count = 1;
        // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    // 如果 nums[i] 比 nums[j] 大，说明可以将 nums[i] 加入以 nums[j] 结尾的上升子序列中
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            // 更新最长上升子序列的长度
            count = max(count, dp[i]);
        }
        return count;
    }
};

int main() {
    cout << "请输入数组元素个数：";
    int n;
    cin >> n;
    vector<int> nums;
    cout << "请输入数组元素：";
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        nums.push_back(num);
    }
    Solution solution;
    int result = solution.lengthOfLIS(nums);
    cout << "最长上升子序列的长度为：" << result << endl;
    return 0;
}